The present invention relates generally to memory management in an interactive system, and in particular, the present invention relates to adaptive scheduling of a mark and sweep garbage collection process in an interactive system.
Efficient use of memory and memory management strategies are important factors to be considered in an interactive system that utilizes a programming language with automatic memory management, such as Java for example. In such an interactive system, certain portions of memory are allocated to define objects, such as mouse events, user interface components, database records, and so forth, to enable those objects to be stored. Since the amount of memory of the system is limited, it is important to identify and reclaim memory allocated to obsolete objects, or previously defined objects that are no longer required for use by existing objects, in order to enable the memory associated with the obsolete objects to be re-used to perform other functions, such as creating new objects. This process of identifying and reclaiming memory previously allocated to objects that have become obsolete is commonly referred to as xe2x80x9cgarbage collectionxe2x80x9d. Implementation of the garbage collection process is typically accomplished using a garbage collection algorithm.
One such conventional garbage collection algorithm, referred to as mark and sweep garbage collection, involves the combined operation of a mark phase and a sweep phase. During operations of the system, a tree of objects, starting at a root object that is retained while the system is running, is stored in the system memory. During the mark phase, the tree is traversed, and all objects that are part of the tree are marked as being in use. Base objects, or root objects of trees are identified or marked as not being garbage and therefore not to be collected. Relationships between the root objects and all secondary objects referenced by the root objects are defined. By being part of a tree, secondary objects that are implicitly referenced by a root object of the tree are required for use by that root object and are therefore be marked so as not to be collected. On the other hand, any secondary objects that are not implicitly referenced by an object of the tree are not required for use and are therefore left unmarked. Once the mark phase is completed, it is assumed that any unmarked object in memory is no longer referenced and is therefore garbage that can be collected. During the sweep phase that follows, enumerated objects in memory that are unmarked are deallocated to enable the corresponding memory to be recovered and reused.
In order to ensure accuracy in the marking of objects during the mark phase, changes to the tree cannot be allowed to occur while the mark operation is performed. If changes were to take place during the mark operation, objects could possibly be incorrectly marked as being in use when they are no longer referenced, or left unmarked when in fact they are referenced and therefore should be marked as objects in use. As a result, all threads or operations of the system, other than the one performing garbage collection, must be halted during the garbage collection operation to ensure that the tree remains stable and the mark phase is accurate.
A user of an interactive system tends to have certain expectations of how quickly the system responds when certain input events are performed, and these expectations vary between input events. For example, a user will typically expect an instantaneous response from the system when performing certain input commands, such as during input events relating to the creation or editing of text, scrolling through a list, playing a game, and so forth. On the other hand, the user will not expect instantaneous response from the system during other input events, such as switching between screens or programs, for example.
Conventional interface devices that employ a mark and sweep garbage collection operation include an algorithm for determining when to perform the garbage collection process. Conventional algorithms are designed to invoke the mark and sweep garbage collection either after a certain amount of memory has been allocated or after less than a certain amount of memory is free or available. Since memory allocation tends to be unpredictable, it is possible that the garbage collection process of the conventional interface device will be invoked at any time, including during those time periods when the user is performing an input event for which there is a user expectation of instantaneous response from the system.
For example, due to the non-deterministic nature of memory allocation, it is possible that the garbage collection process of conventional interface devices could sometimes take place while the user is scrolling through a list. As a result, for reasons described above, all threads or operations, including operations associated with the scrolling operation being performed by the user, must necessarily be stopped to enable the garbage collection process to be performed. This halting of operations associated with the scrolling performed by the user will directly impact the user since the scrolling will be momentarily halted, contradicting user expectations of an instantaneous response from the system. As a result, the user will tend to view the garbage collection process as an unacceptable and annoying interruption that corrupts user expectations and enjoyment of the system.
Accordingly, what is needed is a garbage collection scheduling scheme that lessens the impact of the garbage collection process on the user.